import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.GeneralPath;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

import javax.imageio.ImageIO;

public class Constellations {

	public static void main(String[] args) {

		//create file for the source  
		File input1 = new File("/afs/cs.wisc.edu/u/h/o/hottinge/Desktop/stars300000.jpg");
		//create a file for the output  
		File output = new File("/afs/cs.wisc.edu/u/h/o/hottinge/Desktop/stars_constellations.jpg");  

		//create the buffered image to load the bitmap into
		BufferedImage image1 = null;
		Pixel currPixel = null;
		Color c = null;
		Queue<Pixel> pixelQueue = new LinkedList<Pixel>();
		int edgeWeight;
		int myRGB;
		final int MAX_COMBINED_PIX_PLUS_1 = 511;

		//read the image of the stars into the bitmap
		try {
			image1 = ImageIO.read(input1);
		} catch (IOException e) {
			e.printStackTrace();
		}

		Config.SKY_WIDTH = image1.getWidth();
		Config.SKY_HEIGHT = image1.getHeight();

		//read each pixel in the image and create a pixel object containing location and brightness
		for (int i = 0; i < image1.getWidth(); i++) {
			for (int j = 0; j < image1.getHeight(); j++) {
				c = new Color(image1.getRGB(i, j));
				//10 for stars.jpg, 50 for messenger_pleadius.jpg
				if (c.getRed() <= 19) continue;
				currPixel = new Pixel(i, j, c.getRed());
				Config.pixels.add(currPixel);
			}
		}
		//create edges from each pixel to every other pixel
		int counter = 1;
		while (counter < Config.pixels.size()) {
			for (int i = counter; i < Config.pixels.size(); i++) {
				pixelQueue.offer(Config.pixels.get(i));
			}

			while (!pixelQueue.isEmpty()) {
				currPixel = pixelQueue.remove();
				edgeWeight = MAX_COMBINED_PIX_PLUS_1 - (currPixel.getRed() + Config.pixels.get(counter-1).getRed());
				Config.edgeList.add(new Edge(Config.pixels.get(counter-1),
						currPixel, edgeWeight));
			}
			counter++;
			System.out.println(counter);
		}

		//sort the edges based on edge weight
		Collections.sort(Config.edgeList);

		//create a union-find data structure for the pixel objects
		UnionFind myUnionFind = new UnionFind(Config.pixels);

		//run kruskals algorithm on the union-find data structure
		kruskal(myUnionFind);

		//set the background of the image to black
		c = Color.BLACK;
		myRGB=c.getRGB();
		for (int i = 0; i < image1.getWidth(); i++) {
			for (int j = 0; j < image1.getHeight(); j++) {
				image1.setRGB(i, j, myRGB);
			}
		}

		//set the highlighting color to yellow and paint all members of the max span tree to the new bitmap
		c = Color.YELLOW;
		myRGB=c.getRGB();

		for (int i = 0; i < Config.maxSpanTreeEdgeList.size(); i++) {
			System.out.println("Edge List...");
			image1.setRGB(Config.maxSpanTreeEdgeList.get(i).getA().getXCoord(), 
					Config.maxSpanTreeEdgeList.get(i).getA().getYCoord(), myRGB);
			image1.setRGB(Config.maxSpanTreeEdgeList.get(i).getB().getXCoord(), 
					Config.maxSpanTreeEdgeList.get(i).getB().getYCoord(), myRGB);
		}

		drawConstellations(image1, c);

		//write the image to the destination as a BMP  
		try {
			ImageIO.write(image1, "jpg", output);
		} catch (IOException e) {
			e.printStackTrace();
		}
		System.out.println("Complete!");
	}

	private static void drawConstellations(BufferedImage image1, Color c) {
		Graphics2D g = image1.createGraphics();
		GeneralPath gp1 = new GeneralPath();
		Random rng = new Random();
		int randomNum;
		int radiusOfStar = 20;
		int counter = 0;
		c = Color.YELLOW;
		while (counter < 15) {
			randomNum = rng.nextInt(Config.edgeList.size());
			if (Config.edgeList.get(randomNum).getEdgeWeight() > 5) continue;
			for (int a = Config.edgeList.get(randomNum).getA().getXCoord() - radiusOfStar; 
			a < Config.edgeList.get(randomNum).getA().getXCoord() + radiusOfStar+1; a++) {
				for (int b = Config.edgeList.get(randomNum).getA().getYCoord() - radiusOfStar; 
				b < Config.edgeList.get(randomNum).getA().getYCoord() + radiusOfStar+1; b ++) {
					if ( !(a < 0) && !(a >= image1.getWidth()) && !(b < 0) &&
							!(b >= image1.getHeight())) {

						if (image1.getRGB(a, b) == c.getRGB()) {
							gp1.moveTo(Config.edgeList.get(randomNum).getA().getXCoord(), 
									Config.edgeList.get(randomNum).getA().getYCoord());
							gp1.lineTo(a, b);
							g.draw(gp1);
						}
					}
				}
			}
			counter++;
		}
	}
	private static void kruskal(UnionFind myUnionFind) {		
		for (int i = 0; i < 300000; i++) {
			System.out.println("Kruskals...");
			// check if A && B have been visited, if so you are about to add a cycle
			if (myUnionFind.connected(Config.edgeList.get(i).getA(), Config.edgeList.get(i).getB())) {
				continue;
			}
			// add the edge weight to Config.maxSpanTreeEdgeList
			Config.maxSpanTreeEdgeList.add(Config.edgeList.get(i));
			// take the union of the sets containing edge A and B
			myUnionFind.union(Config.edgeList.get(i).getA(), Config.edgeList.get(i).getB());
		}
	}
	public static double distance(int x1, int y1, int x2, int y2) {
		return Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
	}

}